package com.bupt.leetcode;

import java.util.LinkedList;

/**
 * 用到栈的算法题目
 * @author Administrator
 *
 */
public class StackProblem {
	/**
	 * 题号：84
	 * https://leetcode.com/problems/largest-rectangle-in-histogram/
	 * ref:http://blog.csdn.net/linhuanmars/article/details/20524507
	 * ref:http://blog.csdn.net/doc_sgl/article/details/11805519
	 * Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
	 * 求直方图最大组成矩形面积。
	 * @param height
	 * @return
	 */
	public int largestRectangleArea(int[] height) {
		if(height == null || height.length == 0) return 0;
		int maxArea = 0;
		LinkedList<Integer> stack = new LinkedList<Integer>();
		for(int i = 0;i<height.length;i++){
			while(!stack.isEmpty() && height[i] < height[stack.peek()]){
				int top = stack.pop();
				int curArea = height[top]*(stack.isEmpty()?i:i-stack.peek()-1);
				maxArea = Math.max(curArea,maxArea);
			}
			stack.push(i);
		}
		while(!stack.isEmpty()){
			int top = stack.pop();
			int curArea = height[top]*(stack.isEmpty()?height.length:height.length-stack.peek()-1);
			maxArea = Math.max(curArea,maxArea);
		}
		return maxArea;
	}
}
